public class Solution440 {
    public int findKthNumber(int n, int k) {
        for (int i=1;i<=9;i++){
            int count=cal(String.valueOf(i),n);
            if (count<k){
                k-=count;
            }else{
                return find(String.valueOf(i),n,k);
            }
        }
        return -1;
    }

    private int find(String start, int n, int k) {
        if (k==1){
            return Integer.parseInt(start);
        }
        k--;
        for (int i=0;i<=9;i++){
            int count=cal(start.concat(String.valueOf(i)),n);
            if (count<k){
                k-=count;
            }else{
                return find(start.concat(String.valueOf(i)),n,k);
            }
        }
        return -1;
    }

    private int cal(String start, int n) {
        int k=1;
        String temp=start;
        String tt=start;
        while (true){
            temp=temp.concat("9");
            tt=tt.concat("0");
            if (Long.parseLong(temp)<=n){
                k+=Math.pow(10,(temp.length()-start.length()));
            }else{
                if (Long.parseLong(tt)<=n){
                    k+=n-Long.parseLong(tt)+1;
                }
                break;
            }
        }
        return k;
    }

    public static void main(String[] args) {
        System.out.println(new Solution440().findKthNumber(1000,1000));
    }
}
